// // 6、【快排的应用】：编写算法，对 n 个关键字取整数值的记录序列进行整理，
// // 以使得所有关键字为负值的关键字排列在关键字为非负值的记录之前，
// // 要求：
// // （1）采用顺序存储结构，至多使用一个记录的辅助存储空间
// // （2）算法的时间复杂度为 O(n)
//
// #include <stdio.h>
// #include <stdlib.h>
// #include <windows.h>
//
// typedef struct SqList {
//     int* data;
//     int length;
//     int maxsize;
// } SqList;
//
// void InitSq(SqList* L) {
//     L->data = NULL;
//     L->length = 0;
//     L->maxsize = 0;
// }
//
// void DestroySq(SqList* L) {
//     free(L->data);
//     L->data = NULL;
//     L->length = L->maxsize = 0;
// }
//
// void FullSq(SqList* L) {
//     if (L->length == L->maxsize) {
//         int newcapacity = (L->maxsize == 0 ? 4 : 2 * L->maxsize);
//         int* tmp = (int*)realloc(L->data, sizeof(int) * newcapacity);
//         if (tmp == NULL) {
//             exit(1);
//         }
//         L->data = tmp;
//         L->maxsize = newcapacity;
//     }
// }
//
// void InsertBack(SqList* L,int e) {
//     FullSq(L);
//     L->data[L->length]=e;
//     L->length++;
// }
//
// void QuickSort(SqList* L) {
//     if(L==NULL||L->data==NULL||L->length<=1) {//注意L==NULL写前面,因为先判断L的属性无法确定L是否被定义
//         return;
//     }
//     int low=0;int high=L->length-1;
//     while (low<high) {
//         while (low<high&&L->data[high]>=0) {
//             high--;
//         }
//         while (low<high&&L->data[low]<0) {
//             low++;
//         }
//         if(low<high) {
//             int temp=L->data[low];
//             L->data[low]=L->data[high];
//             L->data[high]=temp;
//         }
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     SqList list;
//     InitSq(&list);
//
//     // 添加测试数据
//     InsertBack(&list,2);
//     InsertBack(&list,3);
//     InsertBack(&list,5);
//     InsertBack(&list,-2);
//     InsertBack(&list,-9);
//     InsertBack(&list,7);
//     InsertBack(&list,0);
//     InsertBack(&list,-3);
//     InsertBack(&list,11);
//     InsertBack(&list,-5);
//     InsertBack(&list,-3);
//
//     printf("排序前: ");
//     for (int i = 0; i < list.length; i++) {
//         printf("%d ", list.data[i]);
//     }
//
//     QuickSort(&list);
//
//     printf("\n排序后: ");
//     for (int i = 0; i < list.length; i++) {
//         printf("%d ", list.data[i]);
//     }
//
//     DestroySq(&list);
//     return 0;
// }
//
//
//
//
//
//
// // 【算法思想】此题目借助快速排序中子表划分的算法思想对表中的数据进行划分。
// // 附设两个指针 low 和 high，初始时分别指向表的上界和下界